/*
 MIT License
 
 Copyright (c) 2021 Steven Le

 Permission is hereby granted, free of charge, to any person obtaining a copy
 of this software and associated documentation files (the "Software"), to deal
 in the Software without restriction, including without limitation the rights
 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 copies of the Software, and to permit persons to whom the Software is
 furnished to do so, subject to the following conditions:
 
 The above copyright notice and this permission notice shall be included in all
 copies or substantial portions of the Software.
 
 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 SOFTWARE.					
*/

#include <stdio.h>
#include <stdlib.h>

// 创建数据结构：购物单链表
typedef struct buyList
{
	// 购物单链表的下一节点
	struct buyList *nextblp;
	// 购物单中主件的价格
	int main_price;
	// 购物单中主件的优先级
	int priority;
	// 购物单中主件的附件
	int assessory;
	
} BuyList;

/**
 *	通过节点数量n生成新的节点链表。
 *   	参数： 	int n 节点数量
 * 	返回值：	BuyList * 节点链表
 */
BuyList * createBuyList(int n);

/**
 *	获取节点链表bl中的主件价格为mp的元素节点。
 *   	参数： 	int mp 元素节点主件价格
 * 	返回值：	BuyList * 所需节点
 */
BuyList * getBuyListElement(BuyList *bl, int mp);

/**
 *	打印节点链表
 *   	参数： 	无
 * 	返回值：	无
 */
void printBuyList();

/**
 *	给节点链表bl中的末端添加一个元素，值分别为[mp, ap, prio]。
 *   	参数： 	int mp 元素节点主件价格
 *   		int prio 元素节点主件的优先级
 *   		int ap 元素节点主件的附件
 * 	返回值：	无
 */
void addBuyListElement(BuyList *bl, int mp, int prio, int ap); 

/**
 *	给节点链表bl中的更新一个元素，将旧节点oldnode更新为新节点newnode
 *   	参数： 	BuyList *bl 元素列表
 *   		BuyList *newnode 需要更新的新节点
 *   		BuyList *oldnode 已存在的旧结点
 * 	返回值： 	无
 */
void updateBuyListElement(BuyList *bl, BuyList* newnode, BuyList* oldnode); 

/**
 *	删除节点链表bl中主件价格为mp节点
 *	参数： 	BuyList * 节点链表
 *   		int mp 节点链表中主件价格为mp的节点
 * 	返回值： 	无
 */
void deleteBuyListElement(BuyList *bl, int mp); 

/**
 *	对节点链表进行计算，求出不超过总钱数的物品价格与重要度的乘积。
 *	参数： 	BuyList * 节点链表
		int N	总钱数
 * 	返回值： 	int 乘积值 
 * 	  	* -1 代表计算错误， 正常返回正整数的解
 */
int getBuyListSum(BuyList *bl, int N);


int main(void) {
	
	// N 表示总钱数， m 表示希望购买的物品个数 (N < 32000, m < 60)
	int N,m = 0;
	scanf("%d %d", &N, &m); 
	// 创建一个购物单     
	BuyList *blp = createBuyList(m);
	// 添加一个购物单元素
/*
	addBuyListElement(blp, 800, 2, 0);
	addBuyListElement(blp, 400, 5, 1);
	addBuyListElement(blp, 300, 5, 1);
	addBuyListElement(blp, 400, 3, 0);
	addBuyListElement(blp, 500, 2, 0);
*/
	// 新修改一个购物单元素
	// 旧的元素
/*
	BuyList *old = getBuyListElement(blp, 100);
	if (old) {
		// 新的元素
		BuyList *new = (BuyList *)malloc(sizeof(BuyList)); 
		new->main_price = 101;
		new->assessory = 1;
		new->priority = 2;
		updateBuyListElement(blp, new, old);
	}
*/	
	// 删除一个购物单元素
	// deleteBuyListElement(blp, 100, 0, 0);
	// 打印购物单
	// printBuyList(blp);
	// 打印最终解
	if (getBuyListSum(blp, N) != -1)
	{
		printf("%d", getBuyListSum(blp, N));
	}
	// 释放内存空间
	free(blp);	
	return 0;
}

int max(int a,int b){
    return a > b ? a : b;
}

BuyList * createBuyList(int n)
{
	BuyList *head, *node, *end;
	// 注意：头节点不为空
	head = (BuyList *)malloc(sizeof(BuyList));
	end = head;
	for (int i = 0; i < n; i++) {
		node = (BuyList *)malloc(sizeof(BuyList)); 
		scanf("%d %d %d", &node->main_price, &node->priority, &node->assessory);
		end->nextblp = node;
		end = node;
	}
	end->nextblp = NULL;
	return head;
}

BuyList * getBuyListElement(BuyList *bl, int mp)
{
	BuyList *blnode = bl;
	while (blnode != NULL)
	{
		if (blnode->main_price == mp)
			return blnode;
		blnode = blnode->nextblp;
	}
	printf("not found!");
	return NULL;
}

void printBuyList(BuyList *bl)
{
	// 此时需要输出头节点的下一个指针
	BuyList *blnode = bl;
	blnode = blnode->nextblp;
	while (blnode != NULL)
	{
		printf("%d %d %d ---> \n", blnode->main_price, blnode->priority, blnode->assessory);
		blnode = blnode->nextblp;
	}
}

void addBuyListElement(BuyList *bl, int mp, int prio, int ap) 
{
	BuyList *end = bl;
	BuyList *blnode;
	while (end->nextblp != NULL)
	{
		end = end->nextblp;
	}
	blnode = (BuyList *)malloc(sizeof(BuyList));
	blnode->main_price = mp; 
	blnode->priority = prio;
	blnode->assessory  = ap;
	
	end->nextblp = blnode;	
}

void updateBuyListElement(BuyList *bl, BuyList* newnode, BuyList* oldnode) 
{
	BuyList *blnode = bl;
	BuyList *tmp = bl;
	while (blnode != NULL)
	{
		if (blnode->main_price == oldnode->main_price) {
			
			tmp->nextblp = newnode;
			newnode->nextblp = blnode->nextblp;
			blnode = NULL;
			break; 
		}
		
		blnode = blnode->nextblp;
		tmp->nextblp = blnode;
	}
}
 
void deleteBuyListElement(BuyList *bl, int mp)
{
	BuyList *blnode = bl;
	BuyList *rmnode = blnode;
	while(rmnode != NULL)
	{
		if (rmnode->main_price == mp) {
			blnode->nextblp = rmnode->nextblp;
			rmnode = NULL;
			break;
		} 
		rmnode = rmnode->nextblp;
		blnode->nextblp = rmnode;
	}
} 

int getBuyListSum(BuyList *bl, int N)
{
	BuyList *blnode = bl;
	BuyList *head = blnode;
	int sum;
	int maxSum = 0;
	// 剩余金额
	int remainder = 0;

	while(head != NULL) {
		
		blnode = head;

		// printf("blnode\n");
		// printBuyList(blnode);
		// printf("head\n");
		// printBuyList(head);

		sum = 0;
		remainder = N;
		while(blnode != NULL)
		{
			remainder -= blnode->main_price;
			if (remainder > 0) {
				sum += blnode->main_price * blnode->priority;
				blnode = blnode->nextblp;
			} else {
				break;
			}
			// printf("sum = %d, remainder = %d \n", sum, remainder); 
		}
		maxSum = max(sum, maxSum);
		// printf("%d %d\n", sum, maxSum);
		head = head->nextblp;
	}

	return maxSum > 0 ? maxSum : -1;
}
